package main.kotlin.solution

import java.util.*
import kotlin.collections.ArrayList

class LevelOrder {

    class TreeNode(var `val`: Int) {
        var left: TreeNode? = null
        var right: TreeNode? = null
    }

    // 队列遍历法
    fun levelOrder(root: TreeNode?): List<List<Int>> {
        var resultList = ArrayList<List<Int>>()

        var queue:Queue<TreeNode> = LinkedList<TreeNode>()
        queue.add(root)

        while (!queue.isEmpty()){
            val curDataList = ArrayList<Int>()
            var hasChild = false
            for (i in 0 until queue.size){
                val node = queue.poll() ?: continue
                hasChild = true
                curDataList.add(node.`val`)
                queue.add(node.left)
                queue.add(node.right)
            }
            if (hasChild){
                resultList.add(curDataList)
            }
        }

        return resultList
    }

    // For循环遍历法
    fun levelOrder1(root: TreeNode?): List<List<Int>> {
        if (root == null){
            return ArrayList<List<Int>>()
        }

        var curNodeList = ArrayList<TreeNode?>()
        var resultList = ArrayList<List<Int>>()
        curNodeList.add(root)
        while (true){
            val childNodeList = ArrayList<TreeNode?>()
            val childValueList = ArrayList<Int>()

            for (node in curNodeList){
                node?.let {
                    childValueList.add(it.`val`)
                    childNodeList.add(it.left)
                    childNodeList.add(it.right)
                }
            }

            if (childValueList.isEmpty()){
                break
            }

            resultList.add(childValueList)
            curNodeList = childNodeList
        }
        return resultList
    }

}